//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<math.h>
////void Sort(int*parr,int sz)
////{
////	int i = 0;
////	for (i = 0; i < sz - 1; i++)
////	{
////		int ret = 0;
////		int j = 0;
////		for (j = 0; j < sz - 1 - i; j++)
////		{
////			if (parr[j] < parr[j + 1])
////			{
////				ret = parr[j];
////				parr[j] = parr[j + 1];
////				parr[j + 1] = ret;
////			}
////		}
////	}
////}
////void print(int arr[],int sz)
////{
////	int i = 0;
////	for (i = 0; i < sz; i++)
////	{
////		printf("%d ", arr[i]);
////	}
////}
////int main()
////{
////	int arr[] = { 1, 3, 2, 86, 4, 6, 9, 62 };
////	int sz = sizeof(arr) / sizeof(arr[0]);
////	Sort(arr,sz);
////	print(arr,sz);
////	return 0;
////}
////int Change(int x)
////{
////	int count = 0;
////	long sum = 0;
////
////	while (x)
////	{
////		sum += (x % 6)*pow(10, count);
////		count++;
////		x /= 6;
////	}
////	return sum;
////}
////int main()
////{
////	long x = 0;
////	scanf("%d", &x);
////	Change(x);
////	printf("%d", Change(x));
////	return 0;
////}
////int time(int n)
////
////{
////	if (n == 12)
////	{
////		return 2;
////	}
////	else return (n / 12) * 4 + 2;
////
////}
////int main()
////{
////	int n = 0;
////	scanf("%d", &n);
////	int ret=time(n);
////	printf("%d", ret);
////
////	return 0;
////}
////int main()
////{
////
////	int a = 0;
////	int b = 0;
////	
////	int min_ = 0;
////	scanf("%d%d", &a, &b);
////	int c = a%b;
////	long x = a*b;
////	while (c)
////	{
////
////		a = b;
////		b = c;
////		c = a%b;
////	}
////	min_ = x / b;
////	printf("%d", b + min_);
////	return 0;
////}
////int main()
////{
////
////	int ret = 0;
////	while ((ret = getchar()) != EOF)
////	{
////		if (ret<'0' || ret>'9')
////		{
////
////			printf("YES\n");
////		}
////		else
////			printf("NO\n");
////	}
////	return 0;
////}
//int main()
//{
//	int x = 0;
//	scanf("%d",&x);
//	int i = 0;
//	int j = 0;
//	for (i = 1; i <=x; i++)
//	{
//		if (i == 1 || i == x)
//		{
//			for (j = 1; j <= x; j++)
//			{
//				printf("* ");
//			}
//
//		}
//		
//          else
//           {
//			  printf("*");
//			  for (j = 1; j <= x - 2; j++)
//			  {
//				  printf(" ");
//			  }
//          }
//			
//		}
//		printf("\n");
//	}
//	return 0;
//}